/**
 * 
 */
package ro.dta.idbi.model.dynamicpattern;

import java.awt.Color;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

import ro.dta.idbi.interfaces.IGraphIsomorphism;

import com.mxgraph.layout.hierarchical.mxHierarchicalLayout;
import com.mxgraph.model.mxCell;
import com.mxgraph.model.mxGeometry;
import com.mxgraph.model.mxICell;
import com.mxgraph.model.mxIGraphModel;
import com.mxgraph.util.mxConstants;
import com.mxgraph.view.mxGraph;
import com.mxgraph.view.mxStylesheet;

/**
 * Dependency graph for a transaction
 * 
 * @author Tudor Dobrila
 * 
 */
public class DependencyGraph extends mxGraph {

	/**
	 * Hierarchical layout used to layout the graph
	 */
	private mxHierarchicalLayout layout;

	/**
	 * Current ID to be assigned to a vertex
	 */
	private int currentId = 1;

	/**
	 * Ids of the cells in the graph
	 */
	private Hashtable<mxCell, Integer> cellIds;

	/**
	 * Atomic nodes
	 */
	private List<AtomicNode> nodes;

	/**
	 * Hash table of atoms
	 */
	private Hashtable<String, mxICell> atoms;

	/**
	 * Dependency graph class constructor
	 * 
	 * @param model
	 *            Model of the dependency graph
	 */
	public DependencyGraph(mxIGraphModel model) {
		super();
		setAutoSizeCells(true);
		setHtmlLabels(true);
		setCellsEditable(false);
		setCellsResizable(false);
		setCellsDeletable(false);
		setCellsCloneable(false);
		setAllowDanglingEdges(false);
		orderCells(false);
		setConnectableEdges(false);
		setDropEnabled(false);

		final mxStylesheet stylesheet = getStylesheet();
		this.createStylesheets(stylesheet);

		layout = new mxHierarchicalLayout(this);
		atoms = new Hashtable<String, mxICell>();
		cellIds = new Hashtable<mxCell, Integer>();
		nodes = new ArrayList<AtomicNode>();

		if (model != null) {
			setModel(model);
		}
	}

	/**
	 * Dependency graph class constructor
	 * 
	 * @param transformations
	 *            Ordered list of transformations that define the transaction
	 * @throws ParseException
	 *             If one of the transformations in the transaction couldn't be
	 *             parsed
	 */
	public DependencyGraph(String[] transformations) throws ParseException {
		this((mxIGraphModel) null);

		if (transformations != null) {
			PrimitiveParser parser = new PrimitiveParser();
			// Construct the dependency graph
			for (String t : transformations) {
				AtomicNode atom = parser.parse(t);
				if (atom != null) {
					nodes.add(atom);
				} else {
					throw new ParseException("Could not parse command " + t);
				}
			}
			constructGraph();
		}
	}

	/**
	 * Dependency graph class constructor
	 * 
	 * @param nodes
	 *            Array of nodes displayed in the graph
	 * @throws ParseException
	 */
	public DependencyGraph(AtomicNode[] nodes) throws ParseException {
		this((mxIGraphModel) null);
		this.nodes = new ArrayList<AtomicNode>();
		for (AtomicNode node : nodes) {
			this.nodes.add(node);
		}
		constructGraph();
	}

	/**
	 * Construct the graph from the list of nodes
	 */
	private void constructGraph() {
		getModel().beginUpdate();
		for (AtomicNode atom : nodes) {
			cellIds.put(atom, currentId);
			atom.setValue(currentId + ": " + atom.getValue());
			currentId++;
			atoms.put(atom.getName(), atom);
			addCell(atom);

			for (String dep : atom.getDependentObjects()) {
				if (atoms.containsKey(dep)) {
					insertEdge(getDefaultParent(), "", "", atom, atoms.get(dep));
				}
			}
		}
		getModel().endUpdate();
	}

	/**
	 * Get the adjacency matrix of the dependency graph
	 * 
	 * @return Adjacency matrix of the dependency graph
	 */
	public int[][] getAdjacencyMatrix() {
		Object[] vertices = getChildVertices(getDefaultParent());
		int noVertices = vertices.length;
		int[][] result = new int[noVertices][];

		for (int i = 0; i < noVertices; i++) {
			result[i] = new int[noVertices];
			for (int j = 0; j < noVertices; j++) {
				if (getEdgesBetween(vertices[i], vertices[j]).length > 0) {
					result[i][j] = 1;
				}
			}
		}

		return result;
	}

	/**
	 * Check if the two dependency graphs are isomorphic and label consistent
	 * 
	 * @param graph1
	 *            First dependency graph
	 * @param graph2
	 *            Second dependency graph
	 * @param graphIsomorphism
	 *            Isomorphism algorithm to use when checking
	 * @return True if the graphs match, false otherwise
	 */
	public static boolean matches(DependencyGraph graph1, DependencyGraph graph2,
			IGraphIsomorphism graphIsomorphism) {
		return graph1.matches(graph2, graphIsomorphism);
	}

	/**
	 * Check if the current adjacency graph matches another graphs, i.e. are
	 * isomorphic and label consistent
	 * 
	 * @param graph2
	 *            The other dependency graph
	 * @param graphIsomorphism
	 *            Isomorphism algorithm to use when checking
	 * @return True if the graphs match, false otherwise
	 */
	public boolean matches(DependencyGraph graph2, IGraphIsomorphism graphIsomorphism) {
		int[][] graph1Adj = getAdjacencyMatrix();
		int[][] graph2Adj = graph2.getAdjacencyMatrix();
		int[] mapping = graphIsomorphism.areIsomorphic(graph1Adj, graph2Adj);

		if (mapping == null) {
			// Graphs are not isomorphic
			return false;
		}

		return checkLabelConsistency(graph2, mapping);
	}

	/**
	 * Check if the labels of this graph and another graph, that is isomorphic
	 * to this one, are consistent
	 * 
	 * @return True if labels are consistent, false otherwise
	 */
	private boolean checkLabelConsistency(DependencyGraph graph2, int[] mapping) {
		Object[] vertices1 = getChildVertices(getDefaultParent());
		Object[] vertices2 = graph2.getChildVertices(graph2.getDefaultParent());
		int noVertices = vertices1.length;

		for (int i = 0; i < noVertices; i++) {
			mxCell vertex1 = (mxCell) vertices1[i];
			mxCell vertex2 = (mxCell) vertices2[mapping[i]];

			if (!vertex1.getStyle().equals(vertex2.getStyle())) {
				// The two corresponding vertices don't have the same style
				return false;
			} else {
				if (vertex1.getStyle().equals("ATOM")) {
					// The two vertices are atoms
					if (!vertex1.getValue().equals(vertex2.getValue())) {
						return false;
					}
				} else {
					// The two vertices are groups
					Set<String> group1 = getGroupElements(this, vertex1);
					Set<String> group2 = getGroupElements(graph2, vertex2);
					for (String g : group1) {
						if (!group2.contains(g)) {
							return false;
						}
					}
				}
			}
		}

		return true;
	}

	private static Set<String> getGroupElements(mxGraph graph, mxCell cell) {
		Set<String> result = new HashSet<String>();
		Object[] children = graph.getChildVertices(cell);
		for (Object c : children) {
			mxCell crtVertex = (mxCell) c;
			result.add(crtVertex.getValue().toString());
		}

		return result;
	}

	@Override
	public boolean isCellMovable(Object arg0) {
		mxCell cell = (mxCell) arg0;
		if (cell.getParent() != getDefaultParent()) {
			return false;
		}

		return true;
	}

	/**
	 * Group similar elements in the dependency graph
	 */
	public void group() {
		boolean hasChanged = false;
		getModel().beginUpdate();
		do {
			hasChanged = false;
			Object[] nodes = getChildVertices(getDefaultParent());
			Hashtable<List<mxCell>, List<mxCell>> groups = new Hashtable<List<mxCell>, List<mxCell>>();
			Hashtable<mxCell, mxCell> groupMembership = new Hashtable<mxCell, mxCell>();

			for (Object n : nodes) {
				mxCell crtNode = (mxCell) n;
				Object[] edges = getOutgoingEdges(crtNode);
				List<mxCell> cells = new ArrayList<mxCell>();

				for (Object e : edges) {
					mxCell target = (mxCell) ((mxCell) e).getTarget();
					if (!cells.contains(target)) {
						cells.add(target);
					}
				}

				Collections.sort(cells, new NodeComparer());
				if (groups.containsKey(cells)) {
					groups.get(cells).add(crtNode);
					hasChanged = true;
				} else {
					List<mxCell> newGroup = new ArrayList<mxCell>();
					newGroup.add(crtNode);
					groups.put(cells, newGroup);
				}
			}

			// Create groups
			for (Entry<List<mxCell>, List<mxCell>> e : groups.entrySet()) {
				if (e.getValue().size() > 1) {
					// More than two elements, can create a new group
					// First compute the width of the new element
					int width = 0;
					for (mxCell member : e.getValue()) {
						width += member.getGeometry().getWidth() + 10;
					}

					Object grVertex = insertVertex(getDefaultParent(), "", "", 0, 0, width, 30,
							"GROUP");
					cellIds.put((mxCell) grVertex, currentId);
					currentId++;
					int pos = 0;
					for (mxCell member : e.getValue()) {
						getModel().remove(member);
						width = (int) member.getGeometry().getWidth();
						member.setGeometry(new mxGeometry(pos, 5, member.getGeometry().getWidth(),
								member.getGeometry().getHeight()));
						pos += width + 10;
						addCell(member, grVertex);
						groupMembership.put(member, (mxCell) grVertex);

						// Update inbound edges to the group
						Object[] incEdges = getIncomingEdges(member);
						for (Object edge : incEdges) {
							mxCell source = (mxCell) ((mxCell) edge).getSource();
							getModel().remove(edge);
							insertEdge(getDefaultParent(), "", "", source, grVertex);
						}

						Object[] outEdges = getOutgoingEdges(member);
						for (Object edge : outEdges) {
							getModel().remove(edge);
						}
					}

					HashSet<mxCell> targetGroups = new HashSet<mxCell>();
					for (mxCell target : e.getKey()) {
						if (groupMembership.containsKey(target)) {
							targetGroups.add(groupMembership.get(target));
						} else {
							targetGroups.add(target);
						}
					}

					for (mxCell target : targetGroups) {
						insertEdge(getDefaultParent(), "", "", grVertex, target);
					}
				}
			}
		} while (hasChanged);
		getModel().endUpdate();
	}

	/**
	 * Group similar nodes in the dependency graph and collapse similar
	 * instructions in groups
	 */
	public void collapse() {
		this.group();

		Object[] vertices = getChildVertices(getDefaultParent());
		for (Object v : vertices) {
			mxCell crtCell = (mxCell) v;
			if (crtCell.getStyle() != null && crtCell.getStyle().equals("GROUP")) {
				Hashtable<String, Integer> crtGroup = collapseGroup(crtCell);

				// Remove all child vertices
				for (Object o : getChildVertices(crtCell)) {
					getModel().remove(o);
				}

				int pos = 0;
				for (Entry<String, Integer> e : crtGroup.entrySet()) {
					AtomicNode node = new AtomicNode();
					String suffix = "";
					if (e.getValue() > 1) {
						suffix = "*";
					}
					node.setType(e.getKey() + suffix);
					node.setGeometry(new mxGeometry(pos, 5, 120, 20));
					addCell(node, crtCell);
					pos += 130;
				}

				crtCell.getGeometry().setWidth(pos);
			}
		}
	}

	/**
	 * Recursively collapse a group
	 * 
	 * @return Hashtable with transformations and the no. of occurences of each
	 *         transformation
	 */
	private Hashtable<String, Integer> collapseGroup(Object group) {
		Hashtable<String, Integer> result = new Hashtable<String, Integer>();

		Object[] vertices = getChildVertices(group);
		for (Object v : vertices) {
			mxCell crtCell = (mxCell) v;

			if (crtCell.getStyle().equals("GROUP")) {
				Hashtable<String, Integer> crtGroup = collapseGroup(crtCell);
				for (Entry<String, Integer> e : crtGroup.entrySet()) {
					if (!result.containsKey(e.getKey())) {
						result.put(e.getKey(), e.getValue());
					} else {
						Integer i = result.get(e.getKey());
						result.put(e.getKey(), i + e.getValue());
					}
				}
			} else {
				AtomicNode crtNode = (AtomicNode) crtCell;
				if (!result.containsKey(crtNode.getType())) {
					result.put(crtNode.getType(), 1);
				} else {
					Integer i = result.get(crtNode.getType());
					result.put(crtNode.getType(), i + 1);
				}
			}
		}

		return result;
	}

	/**
	 * Create the style sheets used when displaying the schema
	 * 
	 * @param styleSheet
	 *            Style sheet where styles will be added
	 */
	private void createStylesheets(final mxStylesheet styleSheet) {
		mxConstants.VERTEX_SELECTION_COLOR = Color.BLACK;

		// Style for tables
		final Map<String, Object> style = new Hashtable<String, Object>();
		style.put(mxConstants.STYLE_SHAPE, mxConstants.SHAPE_ELLIPSE);
		style.put(mxConstants.STYLE_VERTICAL_ALIGN, mxConstants.ALIGN_TOP);
		style.put(mxConstants.STYLE_FONTSTYLE, mxConstants.FONT_BOLD);
		style.put(mxConstants.STYLE_OPACITY, 50);
		style.put(mxConstants.STYLE_FONTCOLOR, "#000000");
		style.put(mxConstants.STYLE_FONTSIZE, 13);
		styleSheet.putCellStyle("ATOM", style);

		final Map<String, Object> style2 = new Hashtable<String, Object>();
		style2.put(mxConstants.STYLE_SHAPE, mxConstants.SHAPE_RECTANGLE);
		style2.put(mxConstants.STYLE_OPACITY, 50);
		styleSheet.putCellStyle("GROUP", style2);
	}

	/**
	 * Auto-layout of the graph using hierarchical layout
	 */
	public void performLayout() {
		layout.execute(getDefaultParent());
	}

	class NodeComparer implements Comparator<mxICell> {

		@Override
		public int compare(mxICell o1, mxICell o2) {
			return cellIds.get(o1).compareTo(cellIds.get(o2));
		}

	}
}
